package com.yzi.core.collection
{
	public class LinkedList implements ICollection
	{
		private var m_size:int;
		private var m_head:LinkedNode;
		private var m_tail:LinkedNode;
		
		public function LinkedList()
		{
		}
		
		private function insertBetween($current:LinkedNode, $target:LinkedNode): void
		{
			var left:LinkedNode = $current.left;
			left.right = $target;
			$target.left = left;
			$target.right = $current;
			$current.left = $target;
		}
		
		private function removeBetween($current:LinkedNode): void
		{
			var left:LinkedNode = $current.left;
			var right:LinkedNode = $current.right;
			
			if(!left) {
				m_head = right;
				m_head.left = null;
			}
			
			if(!right) {
				m_tail = left;
				m_tail.right = null;
			}
			
			$current.left = null;
			$current.right = null;
		}
		
		public function AddHead($node:LinkedNode): void
		{
			if(!m_head && !m_tail) {
				m_tail = m_head = $node;
			} else {
				$node.right = m_head;
				m_head.left = $node;
				m_head = $node;
			}
			m_size++;
		}
		
		public function AddTail($node:LinkedNode): void
		{
			if(!m_head && !m_tail) {
				m_tail = m_head = $node;
			} else {
				$node.left = m_tail;
				m_tail.right = $node;
				m_tail = $node;
			}
			m_size++;
		}
		
		public function AddAt($node:LinkedNode, $index:uint): void
		{
			if($index > m_size) throw new Error("Out of Range");
			if($index == 0) {
				AddHead($node);
				return;
			}
			
			if($index == m_size) {
				AddTail($node);
				return;
			}
			
			var result:LinkedNode = Get($index);
			insertBetween(result, $node);
			m_size++;
		}
		
		public function RemoveHead(): LinkedNode
		{
			if(!m_head) throw new Error("List is Empty");
			var node:LinkedNode = m_head;
			m_head = m_head.right;
			m_head.left = null;
			node.left = null;
			node.right = null;
			m_size--;
			
			return node;
		}
		
		public function RemoveTail(): LinkedNode
		{
			if(!m_tail) throw new Error("List is Empty");
			var node:LinkedNode = m_tail;
			m_tail = m_tail.left;
			m_tail.right = null;
			node.left = null;
			node.right = null;
			m_size--;
			
			return node;
		}
		
		public function RemoveAt($index:uint): LinkedNode
		{
			var result:LinkedNode = Get($index);
			removeBetween(result);
			m_size--;
			
			return result;
		}
		
		public function Clear():void
		{
			var next:LinkedNode = m_head;
			while(next)
			{
				var current:LinkedNode = next;
				next = current.right;
				current.left = null;
				current.right = null;
			}
			m_head = m_tail = null;
			m_size = 0;
		}
		
		public function Size():int { return m_size; }
		
		public function Get($index:uint): LinkedNode
		{
			if($index >= m_size) throw new Error("Out of Range");
			if($index == 0) return m_head;
			if($index == m_size - 1) return m_tail;
			var result:LinkedNode;
			var cursor:int;
			var next:LinkedNode = m_head;
			while(next)
			{
				var current:LinkedNode = next;
				if($index == cursor) {
					result = current;
					break;
				}
				next = current.right;
				cursor++;
			}
			
			return result;
		}
		
		public function GetIterator(): IIterator { return new LinkedListIterator(this); }
		
		public function IsContain($object:*):Boolean
		{
			var result:Boolean = false;
			var next:LinkedNode = m_head;
			while(next)
			{
				var current:LinkedNode = next;
				if(current == $object) {
					result = true;
					break;
				}
				next = current.right;
			}
			
			return result;
		}
		
		public function IsEmpty():Boolean { return (m_size == 0); }
		
		public function ToArray():Array
		{
			var result:Array = new Array();
			var next:LinkedNode = m_head;
			while(next)
			{
				var current:LinkedNode = next;
				result.push(current);
				next = current.right;
			}
			
			return result;
		}
		
		public function ToString(): String
		{
			var result:String = "";
			var next:LinkedNode = m_head;
			while(next)
			{
				var current:LinkedNode = next;
				result += current.toString() + ", ";
				next = current.right;
			}
			
			return result;
		}
	}
}

import com.yzi.core.collection.IIterator;
import com.yzi.core.collection.LinkedList;
import com.yzi.core.collection.LinkedNode;

internal class LinkedListIterator implements IIterator
{
	private var m_list:LinkedList;
	private var m_cursor:int;
	private var m_size:int;
	
	private var m_node:LinkedNode;
	
	public function LinkedListIterator($list:LinkedList)
	{
		m_list = $list;
		m_cursor = 0;
		m_node = $list.Get(m_cursor);
		m_size = m_list.Size();
	}
	
	public function Next(): *
	{
		var result:LinkedNode = m_node;
		m_node = result.right;
		m_cursor++;
		
		return result;
	}
	
	public function HasNext(): Boolean { return m_cursor < m_size; }
	
	public function Start(): void { m_cursor = 0; }
	
	public function get data(): * { return m_node.item; }
	
	public function set data($object:*): void { m_node.item = $object; }		
}